package Cache;//请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。
//
// 实现 LFUCache 类： 
//
// 
// LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象 
// int get(int key) - 如果键 key 存在于缓存中，则获取键的值，否则返回 -1 。 
// void put(int key, int value) - 如果键 key 已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量 
//capacity 时，则应该在插入新项之前，移除最不经常使用的项。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近最久未使用 的键。 
// 
//
// 为了确定最不常使用的键，可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。 
//
// 当一个键首次插入到缓存中时，它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作，使用计数器的值将会递增。 
//
// 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。 
//
// 
//
// 示例： 
//
// 
//输入：
//["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", 
//"get"]
//[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
//输出：
//[null, null, null, 1, null, -1, 3, null, -1, 3, 4]
//
//解释：
//// cnt(x) = 键 x 的使用计数
//// cache=[] 将显示最后一次使用的顺序（最左边的元素是最近的）
//LFUCache lfu = new LFUCache(2);
//lfu.put(1, 1);   // cache=[1,_], cnt(1)=1
//lfu.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
//lfu.get(1);      // 返回 1
//                 // cache=[1,2], cnt(2)=1, cnt(1)=2
//lfu.put(3, 3);   // 去除键 2 ，因为 cnt(2)=1 ，使用计数最小
//                 // cache=[3,1], cnt(3)=1, cnt(1)=2
//lfu.get(2);      // 返回 -1（未找到）
//lfu.get(3);      // 返回 3
//                 // cache=[3,1], cnt(3)=2, cnt(1)=2
//lfu.put(4, 4);   // 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用
//                 // cache=[4,3], cnt(4)=1, cnt(3)=2
//lfu.get(1);      // 返回 -1（未找到）
//lfu.get(3);      // 返回 3
//                 // cache=[3,4], cnt(4)=1, cnt(3)=3
//lfu.get(4);      // 返回 4
//                 // cache=[3,4], cnt(4)=2, cnt(3)=3 
//
// 
//
// 提示： 
//
// 
// 0 <= capacity <= 10⁴ 
// 0 <= key <= 10⁵ 
// 0 <= value <= 10⁹ 
// 最多调用 2 * 10⁵ 次 get 和 put 方法 
// 
// Related Topics 设计 哈希表 链表 双向链表 👍 529 👎 0

/**
 * LFU  最近最不经常访问的剔除
 * 为了确定最不常使用的键，可以为缓存中的每个键维护一个 使用计数器 。
 * 使用计数最小的键是最久未使用的键。
 *
 * 当一个键首次插入到缓存中时，它的使用计数器被设置为 1 (由于 put 操作)。
 * 对缓存中的键执行 get 或 put 操作，使用计数器的值将会递增。
 *
 *
 * */

import java.util.HashMap;
import java.util.Map;

/**
 * Cache节点
 * */
class Node{
    int key;  //键
    int val;  //值
    int freq = 1;  //初始频率为1
    Node pre;
    Node next;

    public Node() {
    }

    public Node(int key, int val) {
        this.key = key;
        this.val = val;
    }
}
/**
 * 自定义双向链表
 * */
class DoubleLinkedList{

    Node head;
    Node tail;

    /**
     * 初始化，首尾相连
     * */
    public DoubleLinkedList() {
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.pre = head;
    }

    /**
     * 添加节点到头部
     * */
    public void addHead(Node node) {
        head.next.pre = node;
        node.next = head.next;
        head.next = node;
        node.pre = head;
    }

    /**
     * 添加节点到尾部
     * */
    public void addTail(Node node){
        tail.pre.next = node;
        node.pre = tail.pre;
        node.next = tail;
        tail.pre = node;
    }

    /**
     * 删除节点
     * */
    public void deleteNode(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }
}
//leetcode submit region begin(Prohibit modification and deletion)
class LFUCache {

    Map<Integer, Node> cache; // 存储缓存的内容
    Map<Integer, DoubleLinkedList> freqMap; // 存储每个频次对应的双向链表
    int size;  //当前存储数目
    int capacity;  //容量
    int min; // 存储当前最小频次

    public LFUCache(int capacity) {
        cache = new HashMap<>(capacity);
        freqMap = new HashMap<>();
        this.capacity = capacity;
        this.size = 0;
        this.min = 0;
    }

    /**
     * get操作，如果key不存在，则返回-1
     * 如果key存在，则获得元素， 并且加频率加1，将节点加入到对应频次所在的双向链表
     * 如果对应频次所在双向链表不存在，则新建链表加入频次map
     * */
    public int get(int key) {
        if(!cache.containsKey(key)){
            return -1;
        }else{
            Node node = cache.get(key);
            freqInc(node);
            return node.val;
        }
    }

    /**
     * put操作时，要考虑容量问题，
     * 1.如果是已经存在的元素，则频次加1，加入新频次链表
     * 2.是新元素，先预检测容量，容量不够则剔除频次最小的，且最久的的节点
     * 3.否则容量够则添加元素，初始频次为1，加入freqMap
     * */
    public void put(int key, int value) {
        //极端情况下容量为0，不能添加
        if (capacity == 0) {
            return;
        }
        if(cache.containsKey(key)){
            //已经是存在的
            Node node = cache.get(key);
            node.val = value;   //更新新值
            freqInc(node);
        }else{
            //添加的是新元素，预检容量，如果当前容量已达上限，删除频次最小的链表中的节点
            if(size == capacity){
                //获得最小频率链表和cache中节点
                DoubleLinkedList minList = freqMap.get(min);
                //频率相同的删除尾节点
                cache.remove(minList.tail.pre.key);
                minList.deleteNode(minList.tail.pre);
                size--;
            }
            //执行添加操作,添加到cache中和对应频率list中
            Node node = new Node(key, value);  //创建当前节点
            cache.put(key,node);
            DoubleLinkedList list = freqMap.get(node.freq);
            if(list==null){
                //如果链表不存在则新建
                list = new DoubleLinkedList();
                freqMap.put(node.freq,list);
            }
            list.addHead(node);
            size++;
            min = 1;
        }

    }

    /**
     * 向 频率表 添加元素
     *
     * */
    private void freqInc(Node node){
        int oldFreq = node.freq;
        node.freq = oldFreq+1;   // 频次加1
        //需要从原来的频次链表中删除，加入到新的频次链表
        DoubleLinkedList linkedList = freqMap.get(oldFreq);
        linkedList.deleteNode(node);
        //如果当前最小频率和刚删除的节点的频率相同，且删完双向链表为空，则当前节点是原来的最小频次，更新最小频次
        if(min==oldFreq && linkedList.head.next == linkedList.tail){
            min = node.freq;
        }
        //找到新的频次链表
        DoubleLinkedList doubleLinkedList = freqMap.get(oldFreq + 1);
        if(doubleLinkedList==null){
            //说明还没有,则新建
            doubleLinkedList = new DoubleLinkedList();
            freqMap.put(oldFreq + 1, doubleLinkedList);  //添加到频次map中
        }
        //添加到头部，因为头部代表最新访问的
        doubleLinkedList.addHead(node);
    }


}

class Main{
    public static void main(String[] args) {
        // cnt(x) = 键 x 的使用计数
        // cache=[] 将显示最后一次使用的顺序（最左边的元素是最近的）
        LFUCache lfu = new LFUCache(2);
        lfu.put(1, 1);   // cache=[1,_], cnt(1)=1
        lfu.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
        lfu.get(1);      // 返回 1
        // cache=[1,2], cnt(2)=1, cnt(1)=2
        lfu.put(3, 3);   // 去除键 2 ，因为 cnt(2)=1 ，使用计数最小
        // cache=[3,1], cnt(3)=1, cnt(1)=2
        lfu.get(2);      // 返回 -1（未找到）
        lfu.get(3);      // 返回 3
        // cache=[3,1], cnt(3)=2, cnt(1)=2
        lfu.put(4, 4);   // 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用
        // cache=[4,3], cnt(4)=1, cnt(3)=2
        lfu.get(1);      // 返回 -1（未找到）
        lfu.get(3);      // 返回 3
        // cache=[3,4], cnt(4)=1, cnt(3)=3
        lfu.get(4);      // 返回 4
        // cache=[3,4], cnt(4)=2, cnt(3)=3
    }
}


/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
//leetcode submit region end(Prohibit modification and deletion)
